/**
 * @file DoubleLinkedList.h
 * @brief An example of ADT.
 * Reference:
 * Data Structures and Algorithm Analysis in C++ (Fourth Edition),
 * by Mark Allen Weiss.
 * @author linhuo2020 (22235058@zju.edu.cn)
 * @version 1.0
 * @date 2022-09-26
 *
 * @copyright Copyright (c) 2022  by linhuo2020
 *
 */
#ifndef _DOUBLELINKEDLIST_H_
#define _DOUBLELINKEDLIST_H_
#include <iostream>
#include <cstdlib>
#include <initializer_list>
/**
 * @brief A simple doubly linked list.
 * Abstract Data Type.
 *
 * @tparam DT Data type.
 */
template <typename DT>
class DoubleLinkedList
{
private:
    /**
     * @brief The basic doubly linked list node.
     * Nested inside of DoubleLinkedList.
     */
    struct Node
    {
        DT data;
        Node *prev;
        Node *next;
        Node(const DT &d = DT{}, Node *p = nullptr, Node *n = nullptr)
            : data{d}, prev{p}, next{n} {}
        Node(DT &&d, Node *p = nullptr, Node *n = nullptr)
            : data{std::move(d)}, prev{p}, next{n} {}
    };

public:
    class const_iterator
    {
    public:
        const_iterator() : current{nullptr} {}

        const DT &operator*() const { return retrieve(); }

        const_iterator &operator++()
        {
            current = current->next;
            return *this;
        }

        const_iterator operator++(int)
        {
            const_iterator old = *this;
            ++(*this);
            return old;
        }

        const_iterator &operator--()
        {
            current = current->prev;
            return *this;
        }

        const_iterator operator--(int)
        {
            const_iterator old = *this;
            --(*this);
            return old;
        }

        bool operator==(const const_iterator &rhs) const { return current == rhs.current; }

        bool operator!=(const const_iterator &rhs) const { return !(*this == rhs); }

    protected:
        /// @brief A pointer that represents the current position.
        Node *current;
        ///< Can be called by all three versions of operator* without any type conversions.
        DT &retrieve() const { return current->data; }

        const_iterator(Node *p) : current{p} {}

        friend class DoubleLinkedList<DT>;
    };

    class iterator : public const_iterator
    {
    public:
        iterator() {}
        iterator &operator++()
        {
            this->current = this->current->next;
            return *this;
        }

        iterator operator++(int)
        {
            iterator old = *this;
            ++(*this);
            return old;
        }

        iterator &operator--()
        {
            this->current = this->current->prev;
            return *this;
        }

        iterator operator--(int)
        {
            iterator old = *this;
            --(*this);
            return old;
        }
        DT &operator*() { return const_iterator::retrieve(); }
        const DT &operator*() const { return const_iterator::operator*(); }
        iterator(const_iterator p) : const_iterator{p} {}

    protected:
        iterator(Node *p) : const_iterator{p} {}

        friend class DoubleLinkedList<DT>;
    };

public:
    DoubleLinkedList() { init(); }
    DoubleLinkedList(const std::initializer_list<DT> &rhs)
    {
        init();
        for (auto &x : rhs)
            push_back(x);
    }
    DoubleLinkedList(const DoubleLinkedList &rhs)
    {
        init();
        for (auto &x : rhs)
            push_back(x);
    }
    ~DoubleLinkedList()
    {
        clear();
        delete head;
        delete tail;
    }
    DoubleLinkedList &operator=(const DoubleLinkedList &rhs)
    {
        auto copy = rhs;
        std::swap(*this, copy);
        return *this;
    }
    DoubleLinkedList &operator=(DoubleLinkedList &&rhs)
    {
        std::swap(theSize, rhs.theSize);
        std::swap(head, rhs.head);
        std::swap(tail, rhs.tail);
        return *this;
    }
    DoubleLinkedList(DoubleLinkedList &&rhs)
        : theSize{rhs.theSize}, head{rhs.head}, tail{rhs.tail}
    {
        rhs.theSize = 0;
        rhs.head = nullptr;
        rhs.tail = nullptr;
    }

public:
    /**< Return iterator representing beginning of list.
    Mutator version is first, then accessor version.*/
    iterator begin() { return {head->next}; }
    const_iterator begin() const { return {head->next}; }
    /**< Return iterator representing end of list.
    Mutator version is first, then accessor version.*/
    iterator end() { return {tail}; }
    const_iterator end() const { return {tail}; }
    ///< Return number of data currently in the list.
    int size() const { return theSize; }
    ///< Return true if list is empty, otherwise false.
    bool empty() const { return size() == 0; }

    void clear()
    {
        while (!empty())
            pop_front();
    }
    ///============Some Basic Double-ended Queue Operations===============
    DT &front() { return *begin(); }
    const DT &front() const { return *begin(); }
    DT &back() { return *--end(); }
    const DT &back() const { return *--end(); }
    void push_front(const DT &x) { insert(begin(), x); }
    void push_front(DT &&x) { insert(begin(), std::move(x)); }
    void push_back(const DT &x) { insert(end(), x); }
    void push_back(DT &&x) { insert(end(), std::move(x)); }
    void pop_front() { erase(begin()); }
    void pop_end() { erase(--end()); }
    iterator insert(iterator itr, const DT &x)
    {
        Node *p = itr.current;
        theSize++;
        return {p->prev = p->prev->next = new Node{x, p->prev, p}};
    }
    iterator insert(iterator itr, DT &&x)
    {
        Node *p = itr.current;
        theSize++;
        return {p->prev = p->prev->next = new Node{std::move(x), p->prev, p}};
    }
    iterator erase(iterator itr)
    {
        Node *p = itr.current;
        iterator retVal{p->next};
        p->prev->next = p->next;
        p->next->prev = p->prev;
        delete p;
        theSize--;
        return retVal;
    }
    iterator erase(iterator from, iterator to)
    {
        for (iterator itr = from; itr != to;)
            itr = erase(itr);
        return to;
    }
    void printList() const
    {
        if (empty())
        {
            std::cout << "Empty list." << std::endl;
            return;
        }
        for (auto itr = begin(); itr != end(); itr++)
            std::cout << *itr << '\t';
        std::cout << '\b' << std::endl;
    }

private:
    int theSize;
    ///< Sentinel nodes logically representing the beginning/end marker.
    Node *head;
    Node *tail;

    void init()
    {
        theSize = 0;
        head = new Node;
        tail = new Node;
        head->next = tail;
        tail->prev = head;
    }
};

#endif